Push-Down Automaton (PDA)

Extends the concept of an Automaton with a stack, i.e., it can count.

Structure

PDA = (Q,\Sigma,\Gamma,\delta,q_0,F)

• Q: Non-empty set of states
• \Sigma: Input alphabet
• \Gamma: Stack alphabet
• \delta: P Q \times \Sigma_\epsilon \times \Gamma_\epsilon \to \mathcal{P}(Q \times \Sigma_\epsilon)
• q_0: Initial state
• F: Set of valid end states

Lemma: A language is context free if it can be recognized by a PDA. Lemma: A language can be recognized by a PDA if it is context free.